#include <iostream>
#include <vector>

using namespace std;

vector<int> temp;

//将起始下标为left~mid的子数组与下标为mid+1~right的子数组合并（升序
void _merge(vector<int>& nums, int left, int mid, int right) {
    //write ur code here.
    int i = left, j = mid + 1, pos = 0;
    while (i <= mid && j <= right) temp[pos++] = (nums[i] < nums[j] ? nums[i++] : nums[j++]);
    while (i <= mid) temp[pos++] = nums[i++];
    while (j <= right) temp[pos++] = nums[j++];
    while (pos--) nums[left + pos] = temp[pos];
}

//将nums拆分成两部分分别处理后再调用_merge()合并
void _merge_sort(vector<int>& nums, int left, int right) {
    //write ur code here.
    if (left >= right) return;

    int mid = left + ((right - left) >> 1);

    _merge_sort(nums, left, mid);
    _merge_sort(nums, mid + 1, right);

    _merge(nums, left, mid, right);


}

vector<int> MergeSort(vector<int> &nums) {
    temp.resize(nums.size());
    _merge_sort(nums, 0, nums.size() - 1);
    return nums;
}

#include "tools.h"
